Search engines provide a powerful tool for locating documents in a large database of documents, such as the documents on the World Wide Web (WWW) or the documents stored on the storage devices of an Intranet. The documents are located in response to a query submitted by a user. A query typically consists of one or more query terms. To reduce its latency in response to a search request by a user, a search engine may generate a list of predicted queries based on a partial query entered by the user. The user may select a desired one from the ordered list of predicted queries, or may complete the partial query if, e.g., none of the predicted queries corresponds to the query that the user intends to submit.